package study.biggestsequence;

// 吴军的《计算之魂》一书第一章中的一道题：  给定一个实数序列，设计有效算法，找到一个总和最大的区间。
// 复杂度为O(n^3)。
public class Method1 {
    public static void main(String[] args) {

        double[] array = {1.5, -12.3, 3.2, -5.5, 23.2, 3.2, -1.4, -12.2, 34.2, 5.4, -7.8,1.1,-4.9};
        System.out.print(findBiggestSequence(array));
    }

    public static double findBiggestSequence(double[] array) {
        double maxsum = Double.MIN_NORMAL;
        int maxindex = 0;
        int minindex = 0;
        for(int i=0;i<array.length;i++){

            for(int j=i; j<array.length; j++){
                double sum = 0;
                for(int k=i; k<=j; k++){
                    sum += array[k];
                }
                if(sum > maxsum){
                    maxsum = sum;
                    minindex = i;
                    maxindex = j;
//                    System.out.println(sum);
                }
            }
        }
        System.out.println("子数列最大和:"+maxsum);
        System.out.println("和最大子数列的开始位置:"+ (minindex+1));
        System.out.println("和最大子数列的结束位置:"+(maxindex+1));
        return maxsum;
    }
}
